package math;

import org.junit.Test;

public class Ex287 {
    class Solution {
        public int findDuplicate1(int[] nums) {
            int count = 0;
            while (true) {
                boolean flag = false;
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] != i + 1) {
                        if (nums[nums[i] - 1] == nums[i]) {System.out.println(count);return nums[i];}
                        int temp = nums[i];
                        nums[i] = nums[nums[i] - 1];
                        nums[temp - 1] = temp; 
                        flag = true;
                    }
                    count++;
                    
                }
                if (!flag) return -1;
            }
        }

        public int findDuplicate2(int[] nums) {
            int l = 1, r = nums.length - 1, m;
            while (l < r) {
                m = (r + l + 1) >>> 1; //mid是指1~n的数的中间数，若为偶数个，则为靠右那个[如，若最大值为6，则len = 7, 而mid == 4]
                int count = 0;
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] < m) count++;
                }
                if (count > ((l + r) >>> 1)) { // 检测小于mid的数，是否大于一半, 若大于一半，结果必定在前一半
                    r = m - 1;
                } else {
                    l = m;
                }
            }
            return l;
        }

        //设开头到链表环的起点为a, 相遇点到环起点距离为b，则slow走了a+b = n, fast走了a + b + kc = 2n, n = kc
        //循环1：假设slow走了n步，则fast走了2n步， fast多走的n步是在循环中的【链表环】
        //循环2：

        public int findDuplicate(int[] nums) {
            int slow = 0, fast = 0, find = 0;
            while (true) {
                slow = nums[slow];
                fast = nums[nums[fast]];
                if (slow == fast) break;
            }
            while (slow != find) {
                slow = nums[slow];
                find = nums[find];
            }

            return find;
        }
    }

    @Test
    public void test() {
        int[] nums = new int[] {1,3,4,2,2};
        int[] nums1 = new int[] {1,1};
        int[] nums3 = new int[] {1,3,4,2,2};
        int[] nums2 = new int[] {1,1,2};
        int[] nums5 = new int[] {3,1,3,4,2};
        int nums6[] = {7,9,7,4,2,8,7,7,1,5};

        Solution s = new Solution();
        System.out.println(s.findDuplicate(nums));
        System.out.println(s.findDuplicate(nums1));
        System.out.println(s.findDuplicate(nums3));
        System.out.println(s.findDuplicate(nums2));
        System.out.println(s.findDuplicate(nums5));
        // System.out.println(s.findDuplicate1(nums6));

    }
}
